Hybrid coding methods are widely used to efficiently represent video sequences, where temporal prediction is first performed to reduce temporal redundancy in a video sequence and the resultant prediction errors are then encoded. Such coding approaches have been described in technical literature such as, for example, in: Draft of MPEG-2: Test Model 5, ISO/IEC JTC1/SC29/WG11, April 1993; Draft of ITU-T Recommendation H.263, ITU-T SG XV, December 1995; A. N. Netravali and B. G. Haskell, Digital Pictures: Representation, Compression, and Standards, 2.sup.nd Ed., Plenum Press, 1995; and B. Haskell, A. Puri, and A. N. Netravali, Digital Video: An Introduction to MPEG-2, Chapman and Hall, 1997, the disclosures of which are incorporated herein by reference. It is well known that motion compensated prediction following motion estimation removes temporal redundancy very effectively. There have been many proposed motion estimation algorithms, most of which are based on block matching. Such motion estimation approaches have been described in technical literature such as, for example, in: J. R. Jain and A. K. Jain, "Displacement Measurement And Its Application In Interframe Image Coding," IEEE Trans. Communications, vol. COM-29, pp.1799-1808, December 1981; H. G. Musmann, P. Pirsch, and H. J. Gralleer, "Advances In Picture Coding," Proc. IEEE, vol. 73, no. 4, pp.523-548, Aprail 1985; R. Srinivassan and K. R. Rao, "Predictive Coding Based On Efficient Motion Estimation," IEEE Trans. Communications, vol. COM-33, no.8, pp.888-896, August 1985; and N. D. Memon and K. Sayood, "Lossless Compression Of Video Sequences," IEEE Trans. Communications, vol. 44, no. 10, pp.1340-1345, October 1996, the disclosures of which are incorporated herein by reference. The block matching algorithm attempts to find a block in the reference frame which best matches the current block in terms of mean squared difference or mean absolute difference. The block matching approach has been adopted in many video compression standards since it is easy to implement and provides good estimation performance.
A decoder requires motion vector information for the current block or knowledge of all the data used in the motion estimation performed at the encoder to decode the block properly. However, samples used by these motion estimation algorithms are not available at the decoder. Therefore, these prior art motion estimation algorithms require sending overhead bits pertaining to motion vector information for the current block to a corresponding decoder. The burden of sending overhead bits pertaining to motion vector information to the decoder can be extremely heavy, particularly when block matching is performed on a small block or on a pixel basis. Thus, it would be highly advantageous to have a motion estimation process that does not require motion vector information to be transmitted to a decoder.